# 交错字符串
# 给定三个字符串 s1, s2, s3, 验证 s3 是否是由 s1 和 s2 交错组成的。
#
# 示例 1:
#
# 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
# 输出: true
# 示例 2:
#
# 输入: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc"
# 输出: false
import copy
from typing import List


class Solution:
    def __init__(self):
        pass
    
    def isInterleaveCore(self, s1: List[str], s2: List[str], s1_index: List[int], s2_index: List[int], word: str,
                         word_index: int) -> bool:
        """
        传入s3 中的字符,传入 s1 和 s2 的index列表
        :rtype: object
        """
        # 如果s3 所需的内容没有在s1 或 s2 未标注的代码中返回 False
        # 如果s1或者s2的排序内容不是正序的那么返回False
        print(s1)
        print(s2)
        
        s1_result = False
        s2_result = False
        if word_index == self.s3_len:
            return True
        
        if word not in s1:
            s1_result = False
        elif self.s1_len != len(s1_index):
            # 如果在s1 中 选择s1
            # 如果现有索引位位置在最后一个索引之前那么结果为false,传递s3 下一位
            index = s1.index(word)
            s1[index] = ' '
            if len(s1_index) != 0:
                if s1_index[-1] < index:
                    s1_index.append(index)
                    s1_result = self.isInterleaveCore(copy.copy(s1), copy.copy(s2), s1_index, s2_index, self.s3[word_index + 1],
                                                      word_index + 1)
            else:
                s1_index.append(index)
                s1_result = self.isInterleaveCore(copy.copy(s1), copy.copy(s2), s1_index, s2_index, self.s3[word_index + 1], word_index + 1)
        
        if s1_result:
            return s1_result
        
        if word not in s2:
            s2_result = False
        elif self.s2_len != len(s2_index):
            # 如果在s2 中 选择s2
            # 如果现有索引位位置在最后一个索引之前那么结果为false,传递s3 下一位
            index = s2.index(word)
            s2[index] = " "
            if len(s2_index) != 0:
                if s2_index[-1] < index:
                    s2_index.append(index)
                    s2_result = self.isInterleaveCore(s1, s2, s1_index, s2_index, self.s3[word_index + 1],
                                                      word_index + 1)
            else:
                s2_index.append(index)
                s2_result = self.isInterleaveCore(s1, s2, s1_index, s2_index, self.s3[word_index + 1], word_index + 1)

        return s1_result or s2_result
    
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        self.s1 = s1
        self.s2 = s2
        self.s3 = s3
        
        self.s1_len = len(s1)
        self.s2_len = len(s2)
        self.s3_len = len(s3)
        
        return self.isInterleaveCore(list(s1), list(s2), [], [], s3[0], 0)
        """
        # s1 单词对应的索引数组
        s1_index = []
        for s in s1:
            if s3.index(s) == -1:
                return False
            else:
                i = s3.index(s)
                s3_list = list(s3)
                s3_list[i] = ' '
                s3 = "".join(s3_list)
                s1_index.append(i)
        # s2 单词对应的索引数组
        s2_index = []
        for s in s2:
            if s3.index(s) == -1:
                return False
            else:
                i = s3.index(s)
                s3_list = list(s3)
                s3_list[i] = ' '
                s3 = "".join(s3_list)
                s2_index.append(i)
        # 检查升序还是降序
        s1_index_sort = copy.copy(s1_index)
        s2_index_sort = copy.copy(s2_index)
        s1_index_sort.sort()
        s2_index_sort.sort()
        if (s1_index_sort == s1_index) and (s2_index == s2_index_sort):
            return True
        print((s2_index, s2_index_sort))
        return False
        """


def main():
    sol = Solution()
    print(sol.isInterleave(s1="aabcc", s2="dbbca", s3="aadbbcbcac"))


if __name__ == "__main__":
    main()
